package bin_tree.leetcode;

/**
 * @author yuisama
 * @date 2023/03/28 19:57
 * 最近公共祖先问题
 **/
public class Num236_LCA {
    TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        find(root,p,q);
        return lca;
    }
    // 在当前以root为根的二叉树中，能否找到p或q
    private boolean find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        // 先在左子树中寻找p或q
        int left = find(root.left,p,q) ? 1 : 0;
        // 在右子树中寻找p或q
        int right = find(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid == 2) {
            lca = root;
        }
        return left + right + mid > 0;
    }

}